﻿//994. 腐烂的橘子
//在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
//值 0 代表空单元格；
//值 1 代表新鲜橘子；
//值 2 代表腐烂的橘子。
//每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
//返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 - 1 。

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid)
    {
        queue<pair<int, int>> que;
        //统计新鲜橘子
        int m = grid.size();
        int n = grid[0].size();
        int num = 0;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                //新鲜橘子
                if (grid[i][j] == 1)     num++;
                if (grid[i][j] == 2)     que.push({ i,j });
            }
        }
        int ret = 0;
        //BFS
        while (!que.empty())
        {
            int size = que.size();
            for (int i = 0; i < size; i++)
            {
                pair<int, int> arr = que.front();
                que.pop();
                int r = arr.first;
                int c = arr.second;
                //上
                if (r - 1 >= 0 && grid[r - 1][c] == 1)
                {
                    grid[r - 1][c] = 2;
                    que.push({ r - 1,c });
                    num--;
                }
                //下
                if (r + 1 < m && grid[r + 1][c] == 1)
                {
                    grid[r + 1][c] = 2;
                    que.push({ r + 1,c });
                    num--;
                }
                //左
                if (c - 1 >= 0 && grid[r][c - 1] == 1)
                {
                    grid[r][c - 1] = 2;
                    que.push({ r,c - 1 });
                    num--;
                }
                //右
                if (c + 1 < n && grid[r][c + 1] == 1)
                {
                    grid[r][c + 1] = 2;
                    que.push({ r,c + 1 });
                    num--;
                }
            }
            if (!que.empty()) ret++;
        }
        if (num > 0)   ret = -1;
        return ret;
    }
};